package codingStudy.Dynamic.Fibonacci;

import java.util.Scanner;

/**
 * @author dell
 * @category 记忆化搜索
 */
public class Bate2 {
	private static int[] money;// 用于存放中间点计算结果

	static int fio(int x) {
		if (x == 0)
			return 0;
		if (x == 1)
			return 1;
		if (money[x] == -1) {
			money[x] = fio(x - 1) + fio(x - 2);
		}
		return money[x];
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tage = sc.nextInt();
		long start = System.currentTimeMillis();
		money = new int[tage + 1];
		for (int i = 0; i < tage + 1; i++) {
			money[i] = -1;
		}
		int result = fio(tage);
		long end = System.currentTimeMillis();
		long time = end - start;
		System.out.println(result + " " + time + "");
	}

}
